import collections
class Solution(object):
    def maximalNetworkRank(self, n, roads):
        d = collections.defaultdict(int)
        e = collections.defaultdict(set)
        for u, v in roads:
            d[u] += 1
            d[v] += 1
            e[u].add(v)
            e[v].add(u)
        max_len = 0
        for i in range(n):
            for j in range(i + 1, n):
                if j not in e[i]:
                    max_len = max(max_len, d[i] + d[j])
                else:
                    max_len = max(max_len, d[i] + d[j] - 1)
        return max_len


